<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/favicon.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/@fortawesome/fontawesome-free@6.7.2/css/all.min.css" integrity="sha256-dABdfBfUoC8vJUBOwGVdm8L9qlMWaHTIfXt+7GnZCIo=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"blog.csgrandeur.cn","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.22.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"copycode":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"top_n_per_article":1,"unescape":false,"preload":false,"trigger":"auto"}}</script><script src="/js/config.js"></script>

    <meta name="description" content="复杂度理论与分治 本章探讨了算法分析的核心概念，通过求解最大连续和问题展示了不同算法设计策略的效率差异，并引入了复杂性理论、分治法以及它们在优化算法时间复杂度上的应用。从简单的枚举方法到高效的动态规划与分治策略，逐步揭示了解决问题时算法选择的重要性及其对计算资源消耗的深远影响。">
<meta property="og:type" content="article">
<meta property="og:title" content="15.复杂度理论与分治">
<meta property="og:url" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/index.html">
<meta property="og:site_name" content="CSGrandeur&#39;s Thinking">
<meta property="og:description" content="复杂度理论与分治 本章探讨了算法分析的核心概念，通过求解最大连续和问题展示了不同算法设计策略的效率差异，并引入了复杂性理论、分治法以及它们在优化算法时间复杂度上的应用。从简单的枚举方法到高效的动态规划与分治策略，逐步揭示了解决问题时算法选择的重要性及其对计算资源消耗的深远影响。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E9%A2%98%E7%9B%AE.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E5%89%8D%E7%BC%80%E5%92%8C.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E5%88%86%E6%B2%BB.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_DP.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_DP_example.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%B8%90%E8%BF%9B%E6%95%88%E7%8E%87.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E9%80%92%E5%BD%92%E6%A0%91_%E6%9E%84%E9%80%A0.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E9%80%92%E5%BD%92%E6%A0%91_%E8%AE%A1%E7%AE%97%E5%A4%8D%E6%9D%82%E5%BA%A6.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/FFT.svg">
<meta property="article:published_time" content="2025-03-27T02:41:22.000Z">
<meta property="article:modified_time" content="2025-04-02T06:32:45.721Z">
<meta property="article:author" content="CSGrandeur">
<meta property="article:tag" content="ACM">
<meta property="article:tag" content="Algorithm">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E9%A2%98%E7%9B%AE.svg">


<link rel="canonical" href="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/">


<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/","path":"2025-03-27-15-复杂度理论与分治/","title":"15.复杂度理论与分治"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>15.复杂度理论与分治 | CSGrandeur's Thinking</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?7958adf931092425a489778560129144"></script>







  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">CSGrandeur's Thinking</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">Cogito Ergo Sum</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
      <div class="search-header">
        <span class="search-icon">
          <i class="fa fa-search"></i>
        </span>
        <div class="search-input-container">
          <input autocomplete="off" autocapitalize="off" maxlength="80"
                placeholder="搜索..." spellcheck="false"
                type="search" class="search-input">
        </div>
        <span class="popup-btn-close" role="button">
          <i class="fa fa-times-circle"></i>
        </span>
      </div>
      <div class="search-result-container">
        <div class="search-result-icon">
          <i class="fa fa-spinner fa-pulse fa-5x"></i>
        </div>
      </div>
    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB"><span class="nav-number">1.</span> <span class="nav-text">复杂度理论与分治</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%84%9F%E7%9F%A5%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="nav-number">1.1.</span> <span class="nav-text">感知复杂度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%8D%E6%9D%82%E6%80%A7%E7%90%86%E8%AE%BA"><span class="nav-number">1.2.</span> <span class="nav-text">复杂性理论</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="nav-number">1.2.1.</span> <span class="nav-text">空间复杂度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="nav-number">1.2.2.</span> <span class="nav-text">时间复杂度</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E6%B2%BB"><span class="nav-number">1.3.</span> <span class="nav-text">分治</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%88%86%E6%B2%BB%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="nav-number">1.3.1.</span> <span class="nav-text">分治的时间复杂度分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E7%BA%BF%E6%80%A7%E5%B9%B3%E5%9D%87%E6%83%85%E5%86%B5%E7%AC%ACk%E5%B0%8F"><span class="nav-number">1.3.2.</span> <span class="nav-text">例：线性（平均情况）第k小</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9"><span class="nav-number">1.3.3.</span> <span class="nav-text">例：平面最近点对</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E6%B2%BB%E4%BC%98%E5%8C%96%E7%AD%96%E7%95%A5"><span class="nav-number">1.4.</span> <span class="nav-text">分治优化策略</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%BF%AB%E9%80%9F%E5%B9%82"><span class="nav-number">1.4.1.</span> <span class="nav-text">例：快速幂</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%BF%AB%E9%80%9F%E5%B9%82%E8%AE%A1%E7%AE%97%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E7%AC%AC-n-%E9%A1%B9"><span class="nav-number">1.4.2.</span> <span class="nav-text">例：快速幂计算斐波那契数列第
\(n\) 项</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8Bstrassen%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95"><span class="nav-number">1.4.3.</span> <span class="nav-text">例：Strassen矩阵乘法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2"><span class="nav-number">1.4.4.</span> <span class="nav-text">例：快速傅里叶变换</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#fft%E5%8F%8D%E5%8F%98%E6%8D%A2"><span class="nav-number">1.4.4.1.</span> <span class="nav-text">FFT反变换</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%9D%B4%E8%9D%B6%E5%8F%98%E6%8D%A2"><span class="nav-number">1.4.4.2.</span> <span class="nav-text">蝴蝶变换</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%A4%A7%E6%95%B4%E6%95%B0%E4%B9%98%E6%B3%95%E5%8F%82%E8%80%83%E4%BB%A3%E7%A0%81"><span class="nav-number">1.4.4.3.</span> <span class="nav-text">大整数乘法参考代码</span></a></li></ol></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">CSGrandeur</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">72</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">6</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">22</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://blog.csgrandeur.cn/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="CSGrandeur">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="15.复杂度理论与分治 | CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          15.复杂度理论与分治
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2025-03-27 10:41:22" itemprop="dateCreated datePublished" datetime="2025-03-27T10:41:22+08:00">2025-03-27</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2025-04-02 14:32:45" itemprop="dateModified" datetime="2025-04-02T14:32:45+08:00">2025-04-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/" itemprop="url" rel="index"><span itemprop="name">ACM</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/ACMCOURSE/" itemprop="url" rel="index"><span itemprop="name">ACMCOURSE</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody"><h1 id="复杂度理论与分治">复杂度理论与分治</h1>
<p>本章探讨了算法分析的核心概念，通过求解最大连续和问题展示了不同算法设计策略的效率差异，并引入了复杂性理论、分治法以及它们在优化算法时间复杂度上的应用。从简单的枚举方法到高效的动态规划与分治策略，逐步揭示了解决问题时算法选择的重要性及其对计算资源消耗的深远影响。</p>
<span id="more"></span>
<h2 id="感知复杂度">感知复杂度</h2>
<p>给一个数字序列，求解一段连续的数字最大的和</p>
<p>输入：序列长度<span class="math inline">\(n\)</span>，序列<span
class="math inline">\(\{A_1, A_2, \ldots, A_n\}\)</span>，<span
class="math inline">\(A_i\)</span> 为任意整数</p>
<p>输出：找到<span class="math inline">\(1 \leq i \leq j \leq
n\)</span>，使得<span class="math inline">\(A_i + A_{i+1} + \ldots +
A_{j-1} + A_j\)</span>和最大</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E9%A2%98%E7%9B%AE.svg" class="" title="最大连续和">
<p>方法1：枚举所有的连续序列，找和最大的序列</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> best = A[<span class="number">1</span>];                        <span class="comment">// 初始化答案</span></span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++)            <span class="comment">// 枚举起点</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = i; j &lt;= n; j ++) &#123;      <span class="comment">// 枚举终点</span></span><br><span class="line">        <span class="type">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = i; k &lt;= j; k ++)    <span class="comment">// 序列求和</span></span><br><span class="line">            sum += A[k];</span><br><span class="line">        <span class="keyword">if</span>(sum &gt; best) best = sum;      <span class="comment">// 更新答案</span></span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>
<p>对任意输入个数<span class="math inline">\(n\)</span>，加法（
<code>sum += A[k];</code> ）的执行次数<span
class="math inline">\(T(n)\)</span>是多少？</p>
<ul>
<li>第一层for循环 <span class="math inline">\(\sum_{i=1}^n
\ldots\)</span></li>
<li>第二层for循环<span class="math inline">\(\sum_{j=i}^n
\ldots\)</span></li>
<li>第三层for循环<span class="math inline">\(\sum_{k=i}^j 1 = j - i +
1\)</span></li>
</ul>
<p><span class="math inline">\(T(n) = \sum_{i=1}^n \sum_{j=i}^n (j - i +
1) = \frac{n(n+1)(n+2)}{6}\)</span></p>
<p>我们取个比较大的<span
class="math inline">\(n=10,000\)</span>，此时<span
class="math inline">\(T(n)=166,716,670,000\)</span>。</p>
<p>方法2：先计算前缀和，前<span
class="math inline">\(j\)</span>个数的和减去前<span
class="math inline">\(i-1\)</span>个数的和可以方便地得到<span
class="math inline">\(i~j\)</span>这一连续序列的和<span
class="math inline">\(A_i + A_{i+1} + \ldots + A_j\)</span></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">pre[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++) pre[i] = pre[i - <span class="number">1</span>] + A[i];</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i ++) &#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> j = i; j &lt;= n; j ++)</span><br><span class="line">        best = <span class="built_in">max</span>(best, pre[j] - pre[i - <span class="number">1</span>]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>此方法<span class="math inline">\(T(n) = n + \sum_{i=1}^n (n - i + 1)
= n + \frac{n(n+1)}{2}\)</span></p>
<p><span class="math inline">\(n=10,000\)</span>时<span
class="math inline">\(T(n)=50,015,000\)</span></p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E5%89%8D%E7%BC%80%E5%92%8C.svg" class="" title="前缀和">
<p>方法3：递归地划分问题为左右两半，看左半边的解（最大连续和）大，还是右半边的解大，还是从中间往左右延申的一段连续和大。</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_%E5%88%86%E6%B2%BB.svg" class="" title="分治">
<p>此方法<span class="math inline">\(T(n) = 2T(n/2) +
n\)</span>，中间往左右延申最坏情况就是走到头</p>
<p><span class="math inline">\(n=10,000\)</span>时<span
class="math inline">\(T(n) \approx n\log n \approx 130,000\)</span></p>
<p>方法4：考虑这样一个情况，当连续地累加时，只要和不为负，前面累加的值肯定对后面继续累加有贡献，反之若累加到某个位置为负，则可以抛弃前面的累加值。</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_DP.svg" class="" title="DP">
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%9C%80%E5%A4%A7%E8%BF%9E%E7%BB%AD%E5%92%8C_DP_example.svg" class="" title="DP示例">
<p>此方法<span class="math inline">\(T(n) =
n\)</span>，只需要从前往后每个数考虑一次</p>
<p><span class="math inline">\(n=10,000\)</span>时<span
class="math inline">\(T(n)=10,000\)</span></p>
<p>算法不同，处理同一个问题的基础运算次数可能有非常大的差距</p>
<h2 id="复杂性理论">复杂性理论</h2>
<p>算法更关心随着<span class="math inline">\(n\)</span>无限增长，<span
class="math inline">\(T(n)\)</span>的增长速度——<strong style="color:red;">渐进效率</strong></p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E6%B8%90%E8%BF%9B%E6%95%88%E7%8E%87.svg" class="" title="渐进效率">
<p>通常称渐进效率的高低为“阶”的高低，阶更高的函数增长率更高。</p>
<p>表达渐进效率有 5 个符号：</p>
<ul>
<li>大写<span class="math inline">\(O\)</span>，<span
class="math inline">\(f(n) = O(g(n))\)</span>，表示<span
class="math inline">\(f(n)\)</span>的阶不大于<span
class="math inline">\(g(n)\)</span>的阶；</li>
<li>大写<span class="math inline">\(\Omega\)</span>，<span
class="math inline">\(f(n) = \Omega(g(n))\)</span>，表示<span
class="math inline">\(f(n)\)</span>的阶不小于<span
class="math inline">\(g(n)\)</span>的阶；</li>
<li>小写<span class="math inline">\(o\)</span>，<span
class="math inline">\(f(n) = o(g(n))\)</span>，表示<span
class="math inline">\(f(n)\)</span>的阶严格小于<span
class="math inline">\(g(n)\)</span>的阶；</li>
<li>小写<span class="math inline">\(\omega\)</span>，<span
class="math inline">\(f(n) = \omega(g(n))\)</span>，表示<span
class="math inline">\(f(n)\)</span>的阶严格大于<span
class="math inline">\(g(n)\)</span>的阶；</li>
<li>大写<span class="math inline">\(\Theta\)</span>，<span
class="math inline">\(f(n) = \Theta(g(n))\)</span>，表示<span
class="math inline">\(f(n)\)</span>的阶与<span
class="math inline">\(g(n)\)</span>的阶相同。</li>
</ul>
<p>最常用的是大<span
class="math inline">\(O\)</span>表示，注意<strong>不大于</strong>这个描述，即
<span class="math inline">\(n=O(n^2)\)</span>、<span
class="math inline">\(n^2+n=O(n^2)\)</span> 这类表述都是正确的，大 <span
class="math inline">\(O\)</span>
关心的是一个算法复杂度的“上界”，至于是不是严格等于这个上界就不那么重要了，这样更方便评估一个算法的效率是否“可用”。</p>
<p>算法复杂度<span
class="math inline">\(T(n)\)</span>是关于输入规模<span
class="math inline">\(n\)</span>的函数，如果这个函数包含多项，比如 <span
class="math inline">\(5^{n}+2n^{2}+3n\dots\)</span>，大<span
class="math inline">\(O\)</span>表示法只保留阶最高的项，且不关心常数系数，这个例子的大<span
class="math inline">\(O\)</span>表示应该简化为 <span
class="math inline">\(O(5^{n})\)</span></p>
<h3 id="空间复杂度">空间复杂度</h3>
<p>算法启动后需要的额外空间。</p>
<p>通常先指定一个常数级别的基本单位，比如 <code>int</code>（4个字节）
大小的内存、长度为<code>10</code>的<code>char</code>等等，根据具体的算法指定一个合乎逻辑的基本单位，统计基本单位的使用数量，得到一个关于输入规模
<span class="math inline">\(n\)</span> 的函数。</p>
<h3 id="时间复杂度">时间复杂度</h3>
<p>算法基本运算执行的次数，基本运算是一个或一组有限时间内结束的、算法中执行频率最高的运算，比如加法、乘法、比较、常数级别的矩阵乘法等等。</p>
<h2 id="分治">分治</h2>
<p>递归地调用自身解决紧密相关的若干子问题，步骤如下：</p>
<ol type="1">
<li>分解原问题为若干互不相交的子问题<br />
这些子问题是原问题规模较小的实例，与原问题属性相同</li>
<li>解决这些子问题，递归进行<br />
如果子问题规模足够小则直接求解</li>
<li>合并这些子问题的解为原问题的解<br />
递归的各子问题解决完后回到上一层进行合并</li>
</ol>
<p>以归并排序为例</p>
<ol type="1">
<li>分解：待排序的<span
class="math inline">\(n\)</span>个元素序列分解为两个<span
class="math inline">\(n/2\)</span>个元素的序列</li>
<li>解决：递归地对两个子序列执行归并排序，长度为1则直接返回</li>
<li>合并：“回升”阶段将两个已排序的子序列合并为一个已排序的结果</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">MergeSort</span><span class="params">(<span class="type">int</span> a[], <span class="type">int</span> l, <span class="type">int</span> r)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l &gt;= r - <span class="number">1</span>) <span class="keyword">return</span>;     <span class="comment">// 【解决】最小规模</span></span><br><span class="line">    <span class="type">int</span> mid = l + r &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="built_in">MergeSort</span>(a, l, mid);      <span class="comment">// 【分解】并【解决】</span></span><br><span class="line">    <span class="built_in">MergeSort</span>(a, mid, r);      <span class="comment">// 【分解】并【解决】</span></span><br><span class="line">    <span class="comment">// 【合并】阶段开始</span></span><br><span class="line">    <span class="type">int</span> i = l, j = mid, tp = l;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; mid &amp;&amp; j &lt; r) &#123;</span><br><span class="line">        <span class="keyword">if</span>(a[j] &lt; a[i]) tmp[tp ++] = a[j ++];</span><br><span class="line">        <span class="keyword">else</span> tmp[tp ++] = a[i ++];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; mid) tmp[tp ++] = a[i ++];</span><br><span class="line">    <span class="keyword">while</span>(j &lt; r) tmp[tp ++] = a[j ++];</span><br><span class="line">    <span class="built_in">memcpy</span>(a + l, tmp + l, <span class="built_in">sizeof</span>(<span class="type">int</span>) * (r - l));</span><br><span class="line">    <span class="comment">// 【合并】阶段结束，【解决】了当前子问题[l,r)</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="分治的时间复杂度分析">分治的时间复杂度分析</h3>
<p>归并排序要解决 <span class="math inline">\(2\)</span> 个 <span
class="math inline">\(n/2\)</span> 规模的子问题，把 <span
class="math inline">\(2\)</span> 个子问题的结果合并为一个有序数组有
<span class="math inline">\(O(n)\)</span> 的代价，复杂度函数表示为</p>
<p><span class="math inline">\(T(n) = 2T( n/2 ) + O(n)\)</span></p>
<p>这种原始问题（规模为<span
class="math inline">\(n\)</span>）的复杂度<span
class="math inline">\(T(n)\)</span>由拆分的若干个（<span
class="math inline">\(a\)</span>个）、相同方法解决的子问题（<span
class="math inline">\(n\)</span>减小的某个规模）复杂度函数<span
class="math inline">\(T(n/b)\)</span>和合并子问题的复杂度<span
class="math inline">\(f(n)\)</span>组成的式子称为递归式，求得由 <span
class="math inline">\(n\)</span> 的公式直接表达 <span
class="math inline">\(T(n)\)</span>
的结果的过程称为解递归式，递归式的解就是这个分治算法的时间复杂度。典型形式为：</p>
<p>多个相同规模子问题：<span
class="math inline">\(T(n)=aT(n/b)+f(n)\)</span>，
多个不同规模子问题：<span
class="math inline">\(T(n)=T(n/b)+T(n/c)+\dots+f(n)\)</span></p>
<p>最直观的方法是通过<strong>递归树</strong>求解：</p>
<p>每个结点表示单一子问题合并工作的代价（<span
class="math inline">\(f(n)\)</span>），树中每层代价求和，所有层的代价求和</p>
<p>对于<span class="math inline">\(T(n) = 2T(n/2) + n\)</span>，</p>
<p>此处我们仍假设<span class="math inline">\(n\)</span>是2的幂</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E9%80%92%E5%BD%92%E6%A0%91_%E6%9E%84%E9%80%A0.svg" class="" title="递归树构造">
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E9%80%92%E5%BD%92%E6%A0%91_%E8%AE%A1%E7%AE%97%E5%A4%8D%E6%9D%82%E5%BA%A6.svg" class="" title="用递归树计算复杂度">
<h3 id="例线性平均情况第k小">例：线性（平均情况）第k小</h3>
<p><span class="math inline">\(n\)</span>个未排序的数，选择其中第<span
class="math inline">\(k\)</span>小的数。<strong>线性</strong>算法指算法复杂度
<span class="math inline">\(T(n)\)</span> 是关于 <span
class="math inline">\(n\)</span> 的一次函数。</p>
<p>假设数据规模不允许基数排序等特殊排序方法，则快速排序、归并排序等方式需要
<span class="math inline">\(nlogn\)</span>，不满足线性。</p>
<p>设数组为<span
class="math inline">\(S\)</span>，以“快速排序”的思想进行划分</p>
<ol type="1">
<li>分解：选一个数<span
class="math inline">\(m^{*}\)</span>，按大小划分为<span
class="math inline">\(S_1\)</span>和<span
class="math inline">\(S_2\)</span>（<span
class="math inline">\(m^{*}\)</span>在两集合之间），即数组所有比 <span
class="math inline">\(m^{*}\)</span> 小的放它左边，比 <span
class="math inline">\(m^{*}\)</span> 大的放它右边。</li>
<li>解决：
<ul>
<li>若<span class="math inline">\(k \leq |S_1|\)</span>，则在<span
class="math inline">\(S_1\)</span>中找第<span
class="math inline">\(k\)</span>小</li>
<li>若<span class="math inline">\(k &gt; |S_1| + 1\)</span>，则在<span
class="math inline">\(S_2\)</span>中找第<span class="math inline">\(k -
|S_1|\)</span>小</li>
<li>若<span class="math inline">\(k = |S_1| + 1\)</span>，则第<span
class="math inline">\(k\)</span>小为<span
class="math inline">\(m^{*}\)</span></li>
</ul></li>
<li>合并：第<span class="math inline">\(k\)</span>小的数只会存在于<span
class="math inline">\(S_1\)</span>、<span
class="math inline">\(S_2\)</span>、<span
class="math inline">\(m^{*}\)</span>其中一个，在这一边递归找</li>
</ol>
<p>分析：平均情况下，子问题规模（左半边或右半边）<span
class="math inline">\(n/2\)</span>，因为只会在一边找，所以只需要解决
<span class="math inline">\(1\)</span>
个子问题，合并子问题的工作集中在划分这件事上，即“比 <span
class="math inline">\(m^{*}\)</span> 小的放它左边，比 <span
class="math inline">\(m^{*}\)</span> 大的放它右边”，这个操作是 <span
class="math inline">\(O(n)\)</span> 的，所以递归式为：</p>
<p><span class="math inline">\(T(n)=T(n/2)+n\)</span></p>
<p>解递归式得 <span class="math inline">\(T(n)=O(n)\)</span>
，在平均情况下是线性的。</p>
<p>为什么要说“平均情况”呢？因为选<span
class="math inline">\(m^{*}\)</span>划分的时候，有可能大多数都分到了一侧，这种不均衡会导致<span
class="math inline">\(T(n)\)</span>不再是线性的，但选择<span
class="math inline">\(m^{*}\)</span>的随机性很高，可以认为较大概率不会很偏，或从统计角度讲，多次执行的平均运算量是线性的。</p>
<p>其实这个问题有一个理论上更强大的解法，在<strong>最坏情况下</strong>也是<span
class="math inline">\(O(n)\)</span>的，可以在熟练掌握分治后进一步了解。</p>
<p>参考代码</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;complex&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> mod = <span class="number">1e9</span> + <span class="number">7</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e8</span> + <span class="number">10</span>;</span><br><span class="line"><span class="type">int</span> n, m, k;</span><br><span class="line"><span class="type">int</span> a[maxn];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">GetK</span><span class="params">(<span class="type">int</span> left, <span class="type">int</span> right, <span class="type">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left == right - <span class="number">1</span>) <span class="keyword">return</span> a[left];</span><br><span class="line">    <span class="type">int</span> low = left, high = right - <span class="number">1</span>, center = a[low];</span><br><span class="line">    <span class="keyword">while</span>(low &lt; high)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">while</span>(low &lt; high &amp;&amp; a[high] &gt;= center) high --;</span><br><span class="line">        a[low] = a[high];</span><br><span class="line">        <span class="keyword">while</span>(low &lt; high &amp;&amp; a[low] &lt;= center) low ++;</span><br><span class="line">        a[high] = a[low];</span><br><span class="line">    &#125;</span><br><span class="line">    a[low] = center;</span><br><span class="line">    <span class="keyword">if</span>(low - left &gt;= k) <span class="keyword">return</span> <span class="built_in">GetK</span>(left, low, k);</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(low - left + <span class="number">1</span> == k) <span class="keyword">return</span> a[low];</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> <span class="built_in">GetK</span>(low + <span class="number">1</span>, right, k - (low - left) - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>, &amp;n, &amp;m, &amp;k) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        a[<span class="number">0</span>] = m;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; i ++)</span><br><span class="line">            a[i] = <span class="number">1LL</span> * a[i - <span class="number">1</span>] * m % mod;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, <span class="built_in">GetK</span>(<span class="number">0</span>, n, k));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="例平面最近点对">例：平面最近点对</h3>
<p>平面有<span class="math inline">\(n\)</span>个点，位置以<span
class="math inline">\((x,
y)\)</span>坐标表示，求最近的两个点及其距离。</p>
<p>设两个子问题最优解距离为<span class="math inline">\(d\)</span></p>
<p>每个小矩形内至多1个点</p>
<ul>
<li>考虑小矩形内两点最远距离（即对角线<span
class="math inline">\(r\)</span>）</li>
<li><span
class="math inline">\(r=\sqrt{(d/2)^2+(2d/3)^2}=5d/6&lt;d\)</span>，</li>
<li>如有多个点则与子问题最优解矛盾</li>
</ul>
<p>合并时，左侧任一点<span
class="math inline">\(P\)</span>在右侧至多考虑6个点</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9.svg" class="" title="平面最近点对">
<p><span class="math inline">\(T(n)=2T(n/2)+O(n \log n)\)</span>，<span
class="math inline">\(T(n)=O(n \log^2 n)\)</span></p>
<p>虽然左边每个点考查右边 <span class="math inline">\(6\)</span>
个点应当是 <span class="math inline">\(O(n)\)</span>
的，但是要快速找到这 <span class="math inline">\(6\)</span>
个点，就不得不排序，所以合并子问题的工作量稍大了些。</p>
<p>但可以进一步优化，尝试一次排序，在分治的时候同时划分排序信息，避免每次都排序，自行尝试。</p>
<p>参考代码</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e5</span> + <span class="number">10</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> inf = <span class="number">0x3f3f3f3f</span>;     <span class="comment">// 定义一个极大值</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Point</span> &#123;</span><br><span class="line">    <span class="type">int</span> x, y, idx;              <span class="comment">// 坐标及序号</span></span><br><span class="line">    <span class="type">bool</span> <span class="keyword">operator</span>&lt;(<span class="type">const</span> Point &amp;b)&#123;<span class="keyword">return</span> x &lt; b.x;&#125; <span class="comment">// 重载“&lt;”用于排序</span></span><br><span class="line">&#125;;</span><br><span class="line">Point p[maxn], csh[maxn];</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="type">int</span> <span class="title">Sqr</span><span class="params">(<span class="type">int</span> x)</span></span>&#123;<span class="keyword">return</span> x * x;&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Dis</span><span class="params">(Point &amp;a, Point &amp;b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">Sqr</span>(a.x - b.x) + <span class="built_in">Sqr</span>(a.y - b.y);</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">int</span> n, ansa, ansb, ansdis;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Update</span><span class="params">(Point &amp;a, Point &amp;b)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 由于答案要输出点对编号，而不仅仅是距离，用此函数更新答案</span></span><br><span class="line">    <span class="type">int</span> na = a.idx, nb = b.idx, dis = <span class="built_in">Dis</span>(a, b);</span><br><span class="line">    <span class="keyword">if</span>(na &gt; nb) std::<span class="built_in">swap</span>(na, nb);</span><br><span class="line">    <span class="keyword">if</span>(ansdis == <span class="number">-1</span> || dis &lt; ansdis || dis == ansdis &amp;&amp; (na &lt; ansa || na == ansa &amp;&amp; nb &lt; ansb))</span><br><span class="line">        ansa = na, ansb = nb, ansdis = dis;</span><br><span class="line">    <span class="keyword">return</span> dis;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Merge</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> r, <span class="type">int</span> mid)</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> i = l, j = mid, k = l;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; mid &amp;&amp; j &lt; r)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(p[i].y &lt; p[j].y) csh[k ++] = p[i ++];</span><br><span class="line">        <span class="keyword">else</span> csh[k ++] = p[j ++];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(i &lt; mid) csh[k ++] = p[i ++];</span><br><span class="line">    <span class="keyword">while</span>(j &lt; r) csh[k ++] = p[j ++];</span><br><span class="line">    <span class="built_in">memcpy</span>(p + l, csh + l, <span class="built_in">sizeof</span>(Point) * (r - l));</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">JudgeNearby</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> mid, <span class="type">int</span> r, Point &amp;c)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 注意到本算法采用了一个 trick：回溯的同时对 y 坐标做归并排序</span></span><br><span class="line">    <span class="comment">// 说明处理 [l, r) 区间时，[l, mid)和[mid, r)两个子问题已经 y 坐标有序</span></span><br><span class="line">    <span class="comment">// 提取两个子问题到中间点的 x 距离不超过子问题最优解的那些点 pl[] 和 pr[]</span></span><br><span class="line">    <span class="comment">// 只需左右“异步前进”，就能很容易定位左边 pl[] 每个点在右边上下距离不超过当前最优解的那些点</span></span><br><span class="line">    std::vector&lt;Point&gt; pl, pr;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = l; i &lt; mid; i ++)</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">Sqr</span>(c.x - p[i].x) &lt;= ansdis) pl.<span class="built_in">push_back</span>(p[i]);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = mid; i &lt; r; i ++)</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">Sqr</span>(c.x - p[i].x) &lt;= ansdis) pr.<span class="built_in">push_back</span>(p[i]);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>; i &lt; pl.<span class="built_in">size</span>(); i ++) &#123;    <span class="comment">// 对于左侧 pl[] 的每个点</span></span><br><span class="line">        <span class="comment">// 找到右侧 pr[] 的点中距离 pl[i] 小于目前最优解的序号下界 j</span></span><br><span class="line">        <span class="keyword">while</span>(j &lt; pr.<span class="built_in">size</span>() &amp;&amp; pl[i].y &gt; pr[j].y &amp;&amp; <span class="built_in">Sqr</span>(pl[i].y - pr[j].y) &gt; ansdis) j ++;</span><br><span class="line">        <span class="comment">// 从 j 开始枚举 pr[] 中的点，直到 y 坐标距离超过当前最优解</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = j; k &lt; pr.<span class="built_in">size</span>() &amp;&amp; <span class="built_in">Sqr</span>(pl[i].y - pr[k].y) &lt;= ansdis; k ++)</span><br><span class="line">            <span class="built_in">Update</span>(pl[i], pr[k]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">MinDis</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> r)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(r - l &lt;= <span class="number">1</span>) <span class="keyword">return</span> inf;          <span class="comment">// 递归终点：子问题中没有点，返回极大距离</span></span><br><span class="line">    <span class="type">int</span> mid = l + r &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    Point midp = p[mid];</span><br><span class="line">    <span class="built_in">MinDis</span>(l, mid);                     <span class="comment">// 处理子问题最近点对</span></span><br><span class="line">    <span class="built_in">MinDis</span>(mid, r);                     <span class="comment">// 处理子问题最近点对</span></span><br><span class="line">    <span class="built_in">JudgeNearby</span>(l, mid, r, midp);       <span class="comment">// 两侧子问题取相近点求距离更新答案</span></span><br><span class="line">    <span class="built_in">Merge</span>(l, r, mid);                   <span class="comment">// 对 y 坐标进行归并排序的 Merge 操作</span></span><br><span class="line">    <span class="keyword">return</span> ansdis;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n) != EOF) &#123;</span><br><span class="line">        ansa = ansb = ansdis = inf;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++) &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>, &amp;p[i].x, &amp;p[i].y);</span><br><span class="line">            p[i].idx = i;</span><br><span class="line">        &#125;</span><br><span class="line">        std::<span class="built_in">sort</span>(p, p + n);    <span class="comment">// 按重载的“&lt;”，以x从小到大排序</span></span><br><span class="line">        <span class="built_in">MinDis</span>(<span class="number">0</span>, n);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d\n&quot;</span>, ansa, ansb);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="分治优化策略">分治优化策略</h2>
<p><strong>用一部分子问题的解表达另一部分子问题，减少计算子问题的个数</strong></p>
<h3 id="例快速幂">例：快速幂</h3>
<p><span class="math inline">\(a\)</span>为给定实数，<span
class="math inline">\(n\)</span>为自然数，求<span
class="math inline">\(a^n\)</span></p>
<ol type="1">
<li>分解：两份<span class="math inline">\(n/2\)</span>个<span
class="math inline">\(a\)</span>相乘</li>
<li>解决：对于奇数个的子问题，剩下的1个保留，乘在最终结果上</li>
<li>合并：两个子问题的解相乘</li>
</ol>
<p>但两个子问题结果相同，不必递归计算两遍</p>
<p><span class="math inline">\(T(n) = T(n/2) + \Theta(1)\)</span>，<span
class="math inline">\(T(n) = O(\log n)\)</span></p>
<p>奇数个数会有“零头”，这个零头令开一个变量“屯”起来。</p>
<p>问题比较简单，可以“自底向上”地合并，不需要递归了。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">PowMod</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b, <span class="type">int</span> mod)</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> ret = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(;b; b &gt;&gt;= <span class="number">1</span>, a = <span class="number">1LL</span> * a * a % mod)</span><br><span class="line">        <span class="keyword">if</span>(b &amp; <span class="number">1</span>) ret = <span class="number">1LL</span> * ret * a % mod;</span><br><span class="line">    <span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="例快速幂计算斐波那契数列第-n-项">例：快速幂计算斐波那契数列第
<span class="math inline">\(n\)</span> 项</h3>
<p>设<span class="math inline">\(f_0=0\)</span>, <span
class="math inline">\(f_1=1\)</span>, <span
class="math inline">\(f_n=f_{n-1}+f_{n-2}\)</span>，放入2×2的矩阵，发现：</p>
<p><span class="math display">\[
\left(\begin{array}{cc}
f_{n+1} &amp; f_n \\
f_n &amp; f_{n-1}
\end{array}\right)
\times
\left(\begin{array}{cc}
1 &amp; 1 \\
1 &amp; 0
\end{array}\right)
=
\left(\begin{array}{cc}
f_{n+1} + f_n &amp; f_{n+1} \\
f_n + f_{n-1} &amp; f_n
\end{array}\right)
=
\left(\begin{array}{cc}
f_{n+2} &amp; f_{n+1} \\
f_{n+1} &amp; f_n
\end{array}\right)
\]</span></p>
<p>即矩阵每一项都变成了斐波那契数列对应位置的下一项。</p>
<p>从而，</p>
<p><span class="math display">\[
\left(\begin{array}{cc}
f_{n+1} &amp; f_n \\
f_n &amp; f_{n-1}
\end{array}\right)
=
\left(\begin{array}{cc}
1 &amp; 1 \\
1 &amp; 0
\end{array}\right)^n
\]</span></p>
<p>把矩阵类比实数，同样可以用快速幂方法求斐波那契数列第<span
class="math inline">\(n\)</span>项</p>
<p><span class="math inline">\(T(n) = O(\log n)\)</span></p>
<h3 id="例strassen矩阵乘法">例：Strassen矩阵乘法</h3>
<p>求<span class="math inline">\(n\)</span>阶矩阵<span
class="math inline">\(A\)</span>与<span
class="math inline">\(B\)</span>相乘的结果<span
class="math inline">\(AB\)</span>，其中假设<span
class="math inline">\(n=2^k\)</span></p>
<p>直接相乘方法：<span class="math inline">\(T(n)=O(n^3)\)</span></p>
<p>直接分治： 分解： <span class="math display">\[
\left[\begin{array}{cc}
A_{11} &amp; A_{12}\\
A_{21} &amp; A_{22}
\end{array}\right]
\left[\begin{array}{cc}
B_{11} &amp; B_{12}\\
B_{21} &amp; B_{22}
\end{array}\right]
=
\left[\begin{array}{cc}
C_{11} &amp; C_{12}\\
C_{21} &amp; C_{22}
\end{array}\right]
\]</span></p>
<p>求解：递归按矩阵乘规则求各子矩阵相乘结果</p>
<p>合并： <span
class="math display">\[C_{11}=A_{11}B_{11}+A_{12}B_{21}，C_{12}=A_{11}B_{12}+A_{12}B_{22}，\]</span>
<span
class="math display">\[C_{21}=A_{21}B_{11}+A_{22}B_{21}，C_{22}=A_{21}B_{12}+A_{22}B_{22}.\]</span></p>
<p><span
class="math inline">\(T(n)=8T(n/2)+O(n^2)，T(n)=O(n^3)\)</span>——这样不行</p>
<p>子问题定义：两个<span
class="math inline">\(n/2\)</span>规模的子矩阵相乘</p>
<p>优化合并：将<span
class="math inline">\(A_{11}B_{11}\)</span>等8个子问题通过相互表示优化为7个</p>
<p>设<span class="math inline">\(M_1 \sim M_7\)</span>为7个子问题</p>
<p><span class="math display">\[M_1 = A_{11}(B_{12} - B_{22})\]</span>
<span class="math display">\[M_2 = (A_{11} + A_{12})B_{22}\]</span>
<span class="math display">\[M_3 = (A_{21} + A_{22})B_{11}\]</span>
<span class="math display">\[M_4 = A_{22}(B_{21} - B_{11})\]</span>
<span class="math display">\[M_5 = (A_{11} + A_{22})(B_{11} +
B_{22})\]</span> <span class="math display">\[M_6 = (A_{12} -
A_{22})(B_{21} + B_{22})\]</span> <span class="math display">\[M_7 =
(A_{11} - A_{21})(B_{11} + B_{12})\]</span></p>
<p><span class="math display">\[C_{11} = M_5 + M_4 - M_2 + M_6,\]</span>
<span class="math display">\[C_{12} = M_1 + M_2,\]</span> <span
class="math display">\[C_{21} = M_3 + M_4,\]</span> <span
class="math display">\[C_{22} = M_5 + M_1 - M_3 - M_7.\]</span></p>
<p>即Strassen矩阵乘法用7个子问题完成了<span
class="math inline">\(C\)</span>矩阵的计算</p>
<p><span class="math display">\[T(n) = 7T(n/2) + O(n^2)，T(n) =
O(n^{\log 7}) \approx O(n^{2.81})\]</span></p>
<p>Coppersmith-Winograd算法为<span
class="math inline">\(O(n^{2.3727})\)</span></p>
<h3 id="例快速傅里叶变换">例：快速傅里叶变换</h3>
<p>使用FFT解决多项式乘法问题</p>
<p>设两个多项式<span class="math inline">\(F(x)\)</span>和<span
class="math inline">\(G(x)\)</span>如下：</p>
<p><span class="math display">\[
F(x) = a_0 + a_1x + a_2x^2 + \ldots
\]</span></p>
<p><span class="math display">\[
G(x) = b_0 + b_1x + b_2x^2 + \ldots
\]</span></p>
<p>它们的乘积可以表示为：</p>
<p><span class="math display">\[
F(x)G(x) = \sum_{i=0} \sum_{j=0}^{i} a_j b_{i-j} x^i
\]</span></p>
<p>应用到大整数乘法</p>
<p>如果把<span
class="math inline">\(x\)</span>换成10，就解决了大整数乘法问题。例如：</p>
<p><span class="math display">\[
314159 = 9 + 5 \times 10 + 1 \times 10^2 + 4 \times 10^3 + 1 \times 10^4
+ 3 \times 10^5
\]</span></p>
<p>对多项式 <span class="math inline">\(y = a_0 + a_1x + a_2x^2 + \ldots
+ a_{n-1}x^{n-1}\)</span> 做一个反向思考：</p>
<p>A同学有多项式，知道所有系数<span class="math inline">\(a_0, a_1,
\ldots, a_{n-1}\)</span>（都是已知常数）</p>
<p>B同学只知道多项式的形式，但不知道多项式具体是什么</p>
<p>A同学向多项式代入<span class="math inline">\(n\)</span>个不同的<span
class="math inline">\(x_i\)</span>，算出<span
class="math inline">\(n\)</span>个不同的<span
class="math inline">\(y_i\)</span></p>
<p>得到<span class="math inline">\((x_1, y_1), (x_2, y_2), \ldots, (x_n,
y_n)\)</span>，可以视作“点”</p>
<p>思考：B同学拿到<span class="math inline">\(n\)</span>“对”<span
class="math inline">\((x_i, y_i)\)</span>，他能否反向算出<span
class="math inline">\(a_0, a_1, \ldots, a_{n-1}\)</span>的值？</p>
<p><span class="math inline">\(a_0, a_1, \ldots a_{n-1}\)</span>与<span
class="math inline">\((x_1,y_1),(x_2,y_2),\ldots(x_n,y_n)\)</span>都唯一确定一个多项式</p>
<p>系数表示法： <span class="math inline">\(a_0,a_1,\ldots
a_{n-1}\)</span></p>
<p>点值表示法： <span
class="math inline">\((x_1,y_1),(x_2,y_2),\ldots(x_n,y_n)\)</span></p>
<p>系数表示法的多项式乘法是 <span class="math display">\[
F(x)G(x)=\sum_{i=0} \sum_{j=0}^i a_j b_{i-j} x^i
\]</span></p>
<p>思考：点值表示法的多项式乘法如何进行？</p>
<p>对每个特定 <span class="math inline">\(x\)</span>
，两个点表示法的多项式相乘，就是 <span class="math inline">\(y\)</span>
的值相乘。<span
class="math inline">\(F(x)G(x)\)</span>的点值表示法是<span
class="math inline">\((x_1, (y_{a1} * y_{b1})), (x_2, (y_{a2} *
y_{b2})), \ldots\)</span></p>
<p>如何利用点值表示法加速多项式乘法？直接代入<span
class="math inline">\(n\)</span>个不同的<span
class="math inline">\(x\)</span>并不能实质降低复杂度，仍然要<span
class="math inline">\(O(n^2)\)</span>得到所有点值：</p>
<ul>
<li><span class="math inline">\(x_1\)</span> 代入<span
class="math inline">\(F(x)=a_0+a_1 x+\ldots a_{n-1}
x^{n-1}\)</span>得到<span class="math inline">\(y_1\)</span>需要<span
class="math inline">\(O(n)\)</span>时间</li>
<li><span class="math inline">\(n\)</span>个不同的<span
class="math inline">\(x_i\)</span>分别代入，总共就要<span
class="math inline">\(O(n^2)\)</span>的时间</li>
</ul>
<p>设计特殊的<span class="math inline">\(n\)</span>个不同的<span
class="math inline">\(x\)</span>，加速每个点的计算。</p>
<p>复数域下，<span class="math inline">\(x^n=1\)</span>的<span
class="math inline">\(x\)</span>是<span
class="math inline">\(n\)</span>次单位根 <span
class="math display">\[x_k=e^{i 2k\pi/n}, \quad k=0,1,2,\ldots
n-1\]</span></p>
<p>用它作为<span class="math inline">\(n\)</span>个不同的<span
class="math inline">\(x\)</span>，相当于等分了圆周角 <span
class="math display">\[x_k=e^{i 2k\pi/n}=e^{i 2\pi/n
k}=\omega_n^k\]</span></p>
<p>欧拉公式<span class="math inline">\(e^{i2k\pi}=\cos 2k\pi + i \sin
2k\pi = 1\)</span></p>
<p><span class="math inline">\(e^{i2k\pi}\)</span>开<span
class="math inline">\(n\)</span>次根<span class="math inline">\(e^{i
2k\pi/n}\)</span>就是一个解</p>
<img src="/2025-03-27-15-%E5%A4%8D%E6%9D%82%E5%BA%A6%E7%90%86%E8%AE%BA%E4%B8%8E%E5%88%86%E6%B2%BB/FFT.svg" class="" title="FFT">
<p><span class="math inline">\(F(x) = F(\omega_n) = a_0 + a_1 \omega_n +
\ldots + a_{n-1} \omega_n^{n-1}\)</span></p>
<p>奇偶系数分开定义新多项式</p>
<p><span class="math display">\[A(\omega_n) = a_0 + a_2 \omega_n^1 + a_4
\omega_n^2 + \ldots + a_{n-2} \omega_n^{n/2-1}\]</span> <span
class="math display">\[B(\omega_n) = a_1 + a_3 \omega_n^1 + a_5
\omega_n^2 + \ldots + a_{n-1} \omega_n^{n/2-1}\]</span> <span
class="math display">\[F(\omega_n) = A(\omega_n^2) + \omega_n
B(\omega_n^2)\]</span></p>
<p><span class="math inline">\(F(\omega_n) = A(\omega_n^2) + \omega_n
B(\omega_n^2)\)</span>，分别代入<span
class="math inline">\(\omega_n^k\)</span>和<span
class="math inline">\(\omega_n^{k+n/2}\)</span></p>
<p><span class="math inline">\(F(\omega_n^k) = A(\omega_n^{2k}) +
\omega_n^k B(\omega_n^{2k})\)</span> <span class="math inline">\(=
A(\omega_{n/2}^k) + \omega_n^k B(\omega_{n/2}^k)\)</span></p>
<p><span class="math inline">\(F(\omega_n^{k+n/2}) = A(\omega_n^{2k+n})
+ \omega_n^{k+n/2} B(\omega_n^{2k+n})\)</span> <span
class="math inline">\(= A(\omega_{n/2}^k) - \omega_n^k
B(\omega_{n/2}^k)\)</span></p>
<p><span class="math inline">\(F(\omega_n^k) = A(\omega_{n/2}^k) +
\omega_n^k B(\omega_{n/2}^k)\)</span></p>
<p><span class="math inline">\(F(\omega_n^{k+n/2}) = A(\omega_{n/2}^k) -
\omega_n^k B(\omega_{n/2}^k)\)</span></p>
<p>分治！</p>
<p>解决“多项式代入求值”的子问题<span
class="math inline">\(A(\omega_{(n/2)}^k)\)</span>和<span
class="math inline">\(B(\omega_{(n/2)}^k)\)</span> 就能求出<span
class="math inline">\((x_k, y_k)\)</span>，<span
class="math inline">\((x_{(k+n/2)}, y_{(k+n/2)})\)</span>两个点</p>
<p><span class="math inline">\(A(\omega_{n/2}^k)\)</span>和<span
class="math inline">\(B(\omega_{n/2}^k)\)</span>的规模（多项式系数个数）都是原问题的一半</p>
<h4 id="fft反变换">FFT反变换</h4>
<p>前面讨论了如何将多项式从系数表示法转换为点值表示法，现在需要解决如何从点值表示法转换回系数表示法，这个过程称为FFT反变换(IFFT)。</p>
<p>对于点值表示法<span
class="math inline">\((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\)</span>，需要求解方程组（<span
class="math inline">\(a_{i}\)</span>是未知数）：</p>
<p><span class="math display">\[
\begin{cases}
a_0 + a_1x_1 + a_2x_1^2 + \ldots + a_{n-1}x_1^{n-1} = y_1 \\
a_0 + a_1x_2 + a_2x_2^2 + \ldots + a_{n-1}x_2^{n-1} = y_2 \\
\vdots \\
a_0 + a_1x_n + a_2x_n^2 + \ldots + a_{n-1}x_n^{n-1} = y_n
\end{cases}
\]</span></p>
<p>这个方程组可以写成矩阵形式：</p>
<p><span class="math display">\[
\begin{bmatrix}
1 &amp; x_1 &amp; x_1^2 &amp; \ldots &amp; x_1^{n-1} \\
1 &amp; x_2 &amp; x_2^2 &amp; \ldots &amp; x_2^{n-1} \\
\vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
1 &amp; x_n &amp; x_n^2 &amp; \ldots &amp; x_n^{n-1}
\end{bmatrix}
\begin{bmatrix}
a_0 \\
a_1 \\
\vdots \\
a_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
y_1 \\
y_2 \\
\vdots \\
y_n
\end{bmatrix}
\]</span></p>
<p>当<span class="math inline">\(x_k =
\omega_n^k\)</span>时，这个矩阵是范德蒙德矩阵，其逆矩阵有特殊性质。实际上，
IFFT 的矩阵就是 FFT 得到的矩阵的共轭转置除以<span
class="math inline">\(n\)</span>。</p>
<p>因此， IFFT 的计算过程与FFT非常相似，只需要： 1. 将输入序列取共轭 2.
执行FFT 3. 将结果取共轭并除以<span class="math inline">\(n\)</span></p>
<p>所以在FFT代码中改动一小部分逻辑就能完成 IFFT。</p>
<h4 id="蝴蝶变换">蝴蝶变换</h4>
<p><span class="math display">\[A(\omega_n) = a_0 + a_2 \omega_n^1 + a_4
\omega_n^2 + \ldots + a_{n-2} \omega_n^{n/2-1}\]</span> <span
class="math display">\[B(\omega_n) = a_1 + a_3 \omega_n^1 + a_5
\omega_n^2 + \ldots + a_{n-1} \omega_n^{n/2-1}\]</span></p>
<p>观察系数序号与原始多项式的关系，在继续分治过程中，序号变化：</p>
<ul>
<li>初始序号：0, 1, 2, 3, 4, 5, 6, 7</li>
<li>第一次分组：0, 2, 4, 6 | 1, 3, 5, 7</li>
<li>第二次分组：0, 4 | 2, 6 | 1, 5 | 3, 7</li>
</ul>
<p>能否直接得到递归终点的序号序列<br />
0,4 | 2,6 | 1,5 |3,7 的二进制：<br />
000, 100, 010, 110, 001, 101, 011, 111<br />
所有二进制反向：<br />
000, 001, 010, 011, 100, 101, 110, 111</p>
<p>蝴蝶变换代码参考</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">BitRevChange</span><span class="params">(Complex y[], <span class="type">int</span> len)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// len 需要补齐到 2^k</span></span><br><span class="line">    <span class="function">std::vector&lt;<span class="type">int</span>&gt; <span class="title">rev</span><span class="params">(len, <span class="number">0</span>)</span></span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; i ++) &#123;</span><br><span class="line">        rev[i] = rev[i &gt;&gt; <span class="number">1</span>] &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (i &amp; <span class="number">1</span>) rev[i] |= len &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; ++i) </span><br><span class="line">        <span class="keyword">if</span> (i &lt; rev[i]) std::<span class="built_in">swap</span>(y[i], y[rev[i]]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="大整数乘法参考代码">大整数乘法参考代码</h4>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 注释文字由AI阅读代码后生成，仅供参考</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;complex&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="type">const</span> <span class="type">double</span> pi = <span class="built_in">acos</span>(<span class="number">-1</span>);             <span class="comment">// 圆周率，用于计算单位根</span></span><br><span class="line"><span class="type">const</span> <span class="type">double</span> eps = <span class="number">1e-6</span>;                <span class="comment">// 浮点数精度误差</span></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">4e6</span> + <span class="number">10</span>;              <span class="comment">// 最大数组长度，需要是2的幂次</span></span><br><span class="line"><span class="keyword">typedef</span> std::complex&lt;<span class="type">double</span>&gt; Complex;   <span class="comment">// 复数类型，用于FFT计算</span></span><br><span class="line"><span class="type">char</span> a[maxn], b[maxn];                  <span class="comment">// 输入的两个大整数字符串</span></span><br><span class="line">Complex xa[maxn], xb[maxn];             <span class="comment">// 转换为复数数组，用于FFT计算</span></span><br><span class="line"><span class="type">int</span> lena, lenb, len2;                   <span class="comment">// 两个数的长度和FFT计算长度</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 蝴蝶变换：将系数按照二进制反转重新排列</span></span><br><span class="line"><span class="comment">// 例如：000,001,010,011,100,101,110,111 -&gt; 000,100,010,110,001,101,011,111</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">BitRevChange</span><span class="params">(Complex y[], <span class="type">int</span> len)</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="function">std::vector&lt;<span class="type">int</span>&gt; <span class="title">rev</span><span class="params">(len, <span class="number">0</span>)</span></span>;        <span class="comment">// 存储每个位置的反转序号</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; i ++) </span><br><span class="line">    &#123;</span><br><span class="line">        rev[i] = rev[i &gt;&gt; <span class="number">1</span>] &gt;&gt; <span class="number">1</span>;       <span class="comment">// 利用递推关系计算反转序号</span></span><br><span class="line">        <span class="keyword">if</span> (i &amp; <span class="number">1</span>) rev[i] |= len &gt;&gt; <span class="number">1</span>;   <span class="comment">// 处理最低位</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; ++i) </span><br><span class="line">        <span class="keyword">if</span> (i &lt; rev[i]) std::<span class="built_in">swap</span>(y[i], y[rev[i]]);  <span class="comment">// 只交换一次，避免重复</span></span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// FFT主函数：将多项式从系数表示转换为点值表示</span></span><br><span class="line"><span class="comment">// on=1表示FFT，on=-1表示IFFT</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">FFT</span><span class="params">(Complex y[], <span class="type">int</span> len, <span class="type">int</span> on=<span class="number">1</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">BitRevChange</span>(y, len);               <span class="comment">// 先进行蝴蝶变换</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> h = <span class="number">2</span>; h &lt;= len; h &lt;&lt;= <span class="number">1</span>)   <span class="comment">// h是当前处理的子问题规模</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">// 计算单位根：w_n = e^(2πi/n)</span></span><br><span class="line">        <span class="function">Complex <span class="title">wn</span><span class="params">(cos(<span class="number">2</span> * pi / h), on * sin(<span class="number">2</span> * pi / h))</span></span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; len; j += h)  <span class="comment">// 处理每个子问题</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="function">Complex <span class="title">w</span><span class="params">(<span class="number">1</span>, <span class="number">0</span>)</span></span>;             <span class="comment">// 单位根的幂次</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = j; k &lt; j + h / <span class="number">2</span>; k ++)</span><br><span class="line">            &#123;</span><br><span class="line">                Complex u = y[k];        <span class="comment">// 子问题A的结果</span></span><br><span class="line">                Complex t = w * y[k + h / <span class="number">2</span>];  <span class="comment">// 子问题B的结果</span></span><br><span class="line">                y[k] = u + t;            <span class="comment">// 合并结果：A + w*B</span></span><br><span class="line">                y[k + h / <span class="number">2</span>] = u - t;    <span class="comment">// 合并结果：A - w*B</span></span><br><span class="line">                w = w * wn;              <span class="comment">// 更新单位根的幂次</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(on != <span class="number">-1</span>) <span class="keyword">return</span>;                 <span class="comment">// FFT不需要除以n</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; i ++) y[i].<span class="built_in">real</span>(y[i].<span class="built_in">real</span>() / len);  <span class="comment">// IFFT需要除以n</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%s%s&quot;</span>, a, b) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        lena = <span class="built_in">strlen</span>(a); lenb = <span class="built_in">strlen</span>(b);</span><br><span class="line">        <span class="comment">// 将字符串转换为复数数组，注意要倒序存储</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; a[i]; i ++) xa[i] = a[lena - i - <span class="number">1</span>] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; b[i]; i ++) xb[i] = b[lenb - i - <span class="number">1</span>] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 计算FFT需要的长度，必须是2的幂次</span></span><br><span class="line">        <span class="keyword">for</span>(len2 = <span class="number">1</span>; len2 &lt; lena + lenb; len2 &lt;&lt;= <span class="number">1</span>);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 补零到len2长度</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = lena; i &lt; len2; i ++) xa[i] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = lenb; i &lt; len2; i ++) xb[i] = <span class="number">0</span>;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 对两个数进行FFT变换</span></span><br><span class="line">        <span class="built_in">FFT</span>(xa, len2); <span class="built_in">FFT</span>(xb, len2);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 在点值表示下直接相乘</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; len2; i ++) xa[i] *= xb[i];</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 进行IFFT变换，得到乘积的系数表示</span></span><br><span class="line">        <span class="built_in">FFT</span>(xa, len2, <span class="number">-1</span>);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 处理进位，将结果转换回字符串</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; len2; i ++)</span><br><span class="line">        &#123;</span><br><span class="line">            a[i] = (<span class="type">int</span>)(xa[i].<span class="built_in">real</span>() + <span class="number">0.5</span>) % <span class="number">10</span> + <span class="string">&#x27;0&#x27;</span>;  <span class="comment">// 四舍五入并取模</span></span><br><span class="line">            xa[i + <span class="number">1</span>].<span class="built_in">real</span>(xa[i + <span class="number">1</span>].<span class="built_in">real</span>() + (<span class="type">int</span>)(xa[i].<span class="built_in">real</span>() + <span class="number">0.5</span>) / <span class="number">10</span>);  <span class="comment">// 处理进位</span></span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 去除前导零</span></span><br><span class="line">        <span class="keyword">for</span>(lena = len2 - <span class="number">1</span>; a[lena] == <span class="string">&#x27;0&#x27;</span> &amp;&amp; lena &gt; <span class="number">0</span>; lena --);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 输出结果</span></span><br><span class="line">        <span class="keyword">for</span>(; lena &gt;= <span class="number">0</span> &amp;&amp; <span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>, a[lena]); lena --);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/ACM/" rel="tag"># ACM</a>
              <a href="/tags/Algorithm/" rel="tag"># Algorithm</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2025-03-26-14-%E5%9F%BA%E6%9C%AC%E9%80%92%E6%8E%A8/" rel="prev" title="14.基本递推">
                  <i class="fa fa-angle-left"></i> 14.基本递推
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2025-04-02-16-%E5%89%8D%E7%BC%80%E5%92%8C%E3%80%81%E5%B7%AE%E5%88%86/" rel="next" title="16.前缀和、差分">
                  16.前缀和、差分 <i class="fa fa-angle-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments utterances-container"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">

  <div class="copyright">
    &copy; 
    <span itemprop="copyrightYear">2025</span>
    <span class="with-love">
      <i class="fa fa-heart"></i>
    </span>
    <span class="author" itemprop="copyrightHolder">CSGrandeur</span>
  </div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://fastly.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://fastly.jsdelivr.net/npm/@next-theme/pjax@0.6.0/pjax.min.js" integrity="sha256-vxLn1tSKWD4dqbMRyv940UYw4sXgMtYcK6reefzZrao=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/sidebar.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  <script src="https://fastly.jsdelivr.net/npm/hexo-generator-searchdb@1.4.1/dist/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>







  




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://fastly.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


<script class="next-config" data-name="utterances" type="application/json">{"enable":true,"repo":"CSGrandeur/csgrandeur.github.io","issue_term":"pathname","theme":"github-light"}</script>
<script src="/js/third-party/comments/utterances.js"></script>

</body>
</html>
